Imagina que tienes una escala de 8h en una ciudad desconocida, una tarde libre tras un viaje de trabajo o simplemente no tienes plan para un domingo. ¿Cómo planificar una ruta sin perder tiempo y esfuerzo?.De esta necesidad surge la idea de crear una aplicación que crea diferentes itinerarios en función de las necesidades de cada usuario y tiempo disponible.
El objetivo del trabajo es establecer una interfaz que muestre rutas personalizadas a los usuarios en base a:
Punto de partida y llegada
Hora de salida y llegada
Modo de transporte (a pie, coche,)
Preferencias del usuario (museos, puntos emblemáticos, compras, parques,…)
Presupuesto y Rating
En un primer intento se obtuvieron los datos de distintos puntos de interés de Madrid a partir de la API de Google Places.
Dado que una gran parte de los resultados obtenidos provenían de ‘places’ autoeditados por los usuarios y no se disponía del número de reviews de cada lugar para poder evaluar si el lugar era realmente importante o no, se decidió hacer web-scraping de www.tripadvisor.com
En este caso, se ha optado hacerlo únicamente para Madrid para simplificar, pero se podría replicar para más ciudades con relativa facilidad.
De aquí obtuvimos las referencias de 767 puntos de interés asociados a Madrid y más de 2.600 restaurantes de la misma ciudad.
Ver 00.WebScraping.R
La información disponible era:
| nombre | tipo | opiniones | rank |
|---|---|---|---|
| Museo del Prado | Museos especializados | 49563 | 2 |
| Parque del Retiro | Edificios con valor arquitectónico | 47398 | 1 |
| Palacio Real de Madrid | Edificios con valor arquitectónico | 29948 | 5 |
| Mercado San Miguel | Mercadillos | 26483 | 10 |
| Plaza Mayor | Edificios con valor arquitectónico | 22294 | 9 |
| nombre | opiniones | rank | precio | estilo | |
|---|---|---|---|---|---|
| 11529 | Centro asturiano de Madrid | 11 | 3739 | ||
| 17482 | Hermanos Arananz | 1 | 7946 | ||
| 2425 | RESTAURANTE 29 FANEGAS | 238 | 487 | €€ - €€€ | Mediterránea |
| 10053 | La imprenta | 136 | 2907 | €€ - €€€ | Española |
| 12996 | Cocina Asiatica Go | 24 | 4636 | €€ - €€€ | Asiática |
Tanto para los puntos de interés como para los restaurantes se exigió que tuvieran un mínimo de 100 reviews para poder contar con información robusta, y para los restaurantes que además contaran con una valoracíon económica (precio medio) del mismo.
Con esto redujimos los puntos de interés a 158 y los restaurantes a 2.000
Para poder ubicar todos estos puntos, calcular distancias y tiempos entre ellos, se recurrió a la API de GoogleMaps, a partir de la cual se obtuvieron sus coordenadas latitud y longitud. Además de otras características como el rating, dirección,…
| nombre | lat | lon | tipo | Agrupacion | opiniones | rating | |
|---|---|---|---|---|---|---|---|
| 121 | San Sebastian de los Reyes The Style Outlets | 40.56720 | -3.608502 | Centros comerciales | Compras | 155 | 4.200000 |
| 15 | Palacio de Cibeles | 40.41888 | -3.691785 | Edificios con valor arquitectónico | Monumentos y Edificios | 4599 | 4.360145 |
| 11 | Puerta del Sol | 40.41695 | -3.703529 | Puntos emblemáticos y de interés | Puntos emblematicos | 9450 | 4.500000 |
| 87 | Museo del Aire | 40.36496 | -3.804246 | Museos militares | Museos | 293 | 4.600000 |
| 101 | Puerta de Europa - Torres KIO | 40.46670 | -3.688649 | Puntos emblemáticos y de interés | Puntos emblematicos | 236 | 4.300000 |
| nombre | formatted_address | lat | lon | opiniones | rank | precio | rating | |
|---|---|---|---|---|---|---|---|---|
| 771 | El Restaurante Vegetariano | Calle de Angosta de los Mancebos, 6, 28005 Madrid, Spain | 40.41287 | -3.713466 | 126 | 985 | 2 | 4.6 |
| 1810 | Ondinas Do Mendo | Calle de Villaamil, 4, 28039 Madrid, Spain | 40.45684 | -3.705080 | 232 | 310 | 1 | 4.4 |
| 983 | Ginos | Paseo de la Castellana, 278, 28046 Madrid, Spain | 40.47534 | -3.686132 | 186 | 2311 | 2 | 3.8 |
| 679 | El Jardin de Orfila por Mario Sandoval | Calle de Orfila, 6, 28010 Madrid, Spain | 40.42732 | -3.693211 | 260 | 345 | 3 | 4.4 |
| 2444 | The Good Burger | nº, Av. del Monasterio de El Escorial, 30, 28049 Madrid, Spain | 40.50420 | -3.704395 | 193 | 3414 | 1 | 4.0 |
Ver 01.Working_with_Data.R
Fijamos el punto de inicio y fin de la ruta:
Fijamos las horas de inicio y fin de la ruta:
Fijamos el tipo de transporte:
Elegimos la tipología de lugares a visitar y el rango de puntuación de los mismos:
También podemos elegir qué tipo de comida queremos, puntuación y rango de precios:
| Ejemplo |
|---|
| Punto Inicio: Puerta del Sol, Madrid , Punto Final: Plaza de Colon, Madrid |
| Hora Inicio: 8 , Hora Final: 17 |
| Modo de Transporte: caminando |
| Tipo de lugares a visitar: Museos con una puntuación entre: 4 y 5 |
| Tipo de comida: Española con una puntuación entre: 4.5 y 5, y un precio (1 a 3) de: 2 |
Dado que tenemos unos 2.200 puntos entre lugares de interés y restaurantes, si quisiéramos obtener todas las distancias entre los puntos necesitaríamos una matriz con casi 5millones de combinaciones. Trabajar con un matriz de distancias haría que el proceso de cálculo fuera lento y nos obligaríamos a relizar un número muy elevado de consultas a la API de Google Maps con su correspondiente coste.
Para ello, vamos a crear dos modelos de estimación de tiempos en base a:
Las distancias calculadas con la Fórmula de Haversine https://en.wikipedia.org/wiki/Haversine_formula
Las distancias en tiempo obtenidos mediante la API de Google Maps.
Para esto, cogemos 1.000 puntos aletorios de Madrid, y los agrupamos en pares de puntos (500 pares),calculando las distancias y los tiempos para estos 500 ‘trayectos’.
Con estas 500 combianciones y mediante regresiones lm(), creamos los modelos de estimación de tiempos.
Modelo caminando: podemos estimar el tiempo que hay caminando entre dos puntos, a partir de sus coordenadas.
Dado que los tiempos en coche dependen de muchos más factores que si lo hiciéramos andando, incluimos en el modelo más variables como la franja horaria y tipo de trayecto.
Modelo en coche: podemos estimar el tiempo en coche entre dos puntos, a partir de sus coordenadas, de la franja horaria (simplificada en mañana y tarde) y de si trata de un desplazamiento dentro de la M30, fuera o mixto.
Ver 02.Estimation_Models.R
Una vez que tenemos los modelos de estimación podemos calcular los tiempos entre todos los puntos que tenemos.
Dado que trabajar con matrices de tiempos puede resultar algo lento si se trabaja con todas las posibles combinaciones, filtramos de antemano las selecciones que haya hecho el usuario, reduciendo la cantidad de combinaciones posibles y el tiempo de cálculo.
Para ello creamos una función que calcula las distancias entre las coordenadas del punto inicial y final de la ruta que hemos planteado, respecto a las coordenadas de todos los puntos de interés.
A continuación transformamos estas distancias en tiempos, a partir de los modelos que ya hemos creado en el punto 3. Modelos de estimación de tiempos.
Ver 03.Functions.R
A la hora de crear la ruta, tendremos en cuenta otros factores como:
Para esto ponderaremos estos 3 factores para crear un único factor de importancia.
Ver 04.Algorithm.R
El problema al que nos enfrentamos es un problema clásico de la Estadística.
Se trata del problema del Vendedor Viajante (Travel Salesman Problem)
El tiempo disponible para realizar la ruta será la diferencia entre la hora final y la inicial, menos el tiempo que dediquemos a comer (si aplica)
Ahora reordenamos las matrices de tiempos teniendo en cuenta la importancia de los puntos de interés, según los criterios del punto 5.1.
Para eso, partimos de la ruta más sencilla posible que es ir del punto inicial al final, observamos el tiempo necesario para ir de un punto al otro y vemos si está dentro de nuestro tiempo disponible.
Creamos una función que va añadiendo puntos uno a uno en función de la importancia de los puntos y aplicamos el TSP, agregando los tiempos necesarios para recorrer la ruta y evaluando si está dentro de nuestro tiempo disponible. Esto se repite hasta que encuentre la ruta que más se ajusta al tiempo y el orden óptimo de para recorrerla.
Ver 04.Algorithm.R
Ordenamos la ruta con lo que nos devuelve el TSP.
| X | lat | lon | nombre | tipo | rating | opiniones | tiempoNecesario |
|---|---|---|---|---|---|---|---|
| 1 | 40.42512 | -3.690241 | Plaza de Colón, Madrid, Spain | Fin | – | – | 0 |
| 2 | 40.41604 | -3.694925 | Museo Nacional Thyssen-Bornemisza | Museos especializados | 4.6 | 14587 | 120 |
| 11 | 40.41378 | -3.692127 | Museo del Prado | Museos especializados | 4.7 | 49563 | 120 |
| 3 | 40.40791 | -3.694557 | Museo Nacional Centro de Arte Reina Sofía | Museos de arte | 4.5 | 14202 | 120 |
| 5 | 40.41695 | -3.703529 | Plaza de la Puerta del Sol, s/n, 28013 Madrid, Spain | Inicio | – | – | 0 |
Añadimos el tiempo que se tarda en llegar desde cada punto al siguiente, teniendo en cuenta el tiempo que pasaremos en cada punto. Esto se definió en función de la tipología del sitio. Por ejemplo: aproximadamente 2 horas para ver los museos.
| X | lat | lon | nombre | tiempoNecesario | tiempoCoche | tiempoCaminando | id |
|---|---|---|---|---|---|---|---|
| 5 | 40.41695 | -3.703529 | Plaza de la Puerta del Sol, s/n, 28013 Madrid, Spain | 0 | NA | NA | 5 |
| 3 | 40.40791 | -3.694557 | Museo Nacional Centro de Arte Reina Sofía | 120 | 11 | 20 | 4 |
| 11 | 40.41378 | -3.692127 | Museo del Prado | 120 | 11 | 9 | 3 |
| 2 | 40.41604 | -3.694925 | Museo Nacional Thyssen-Bornemisza | 120 | 10 | 5 | 2 |
| 1 | 40.42512 | -3.690241 | Plaza de Colón, Madrid, Spain | 0 | 11 | 17 | 1 |
Después de acumular los tiempos, se calcula entre qué dos puntos habría que hacer una parada para comer, estimada en el entorno de las 14:30.
Para simplificar las combinaciones, nos quedamos con los restaurantes que cumplen con la selección del usuario, y se prioriza en función de la distancia al punto anterior y siguiente.
Para elegir el restaurante, creamos una función con la que nos quedamos con los restaurantes que están a una distancia similar a la distancia que hay al siguiente punto más ‘un retraso’ (por si no hay ninguno cerca y tenemos que alejarnos). Si no encontramos nada a esa distancia, vamos aumentando el retraso 1min hasta un máximo de 30min, para poder encontrar un sitio. Si aún así no hay ninguno, no habrá parada para comer.
| X | lat | lon | name | rating | opiniones | precio | Espanola | distLugCami | criterio |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 40.41254 | -3.695427 | Moratin | 4.7 | 115 | 2 | 1 | 10.39776 | 7.553838 |
| X.1 | X | lat | lon | nombre | tiempoNecesario | tiempoCoche | tiempoCaminando | id |
|---|---|---|---|---|---|---|---|---|
| 1 | 5 | 40.41695 | -3.703529 | Plaza de la Puerta del Sol, s/n, 28013 Madrid, Spain | 0 | NA | NA | 5 |
| 2 | 3 | 40.40791 | -3.694557 | Museo Nacional Centro de Arte Reina Sofía | 120 | 11 | 20 | 4 |
| 3 | 11 | 40.41378 | -3.692127 | Museo del Prado | 120 | 11 | 9 | 3 |
| 4 | 1 | 40.41254 | -3.695427 | Moratín | 60 | NA | 10 | 6 |
| 41 | 2 | 40.41604 | -3.694925 | Museo Nacional Thyssen-Bornemisza | 120 | 10 | 5 | 2 |
| 5 | 1 | 40.42512 | -3.690241 | Plaza de Colón, Madrid, Spain | 0 | 11 | 17 | 1 |
El resultado final es un archivo html, que te muestra la selección, la ruta con las paradas y un detalle de las mismas si nos colocamos encima del ‘pin’.
El resultado final es un ShinyApp donde el usuario puede crear su propia ruta en base a sus preferencias
https://mdomingosancho.shinyapps.io/MyStopOverApp
Ver 05.MyStopOverApp.R